package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.HashMap;

/**
 * 好吧，这个自己实现了一个 5% 的版本，最后看了答案
 * @author qidi
 * @date 2022-01-04 14:42:25
 */
class Q0105_ConstructBinaryTreeFromPreorderAndInorderTraversal {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        HashMap<Integer, Integer> map = null;

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            int len = inorder.length;
            if (len == 0) return null;
            if (len == 1) return new TreeNode(preorder[0]);

            map = new HashMap();
            for (int i = 0; i < len; i++) {
                map.put(inorder[i], i);
            }

            TreeNode node = process(preorder, inorder, 0, len - 1, 0, len - 1);
            return node;
        }

        /**
         * @param pl 前序左边界
         * @param pr 前序右边界
         * @param il 中序左边界
         * @param ir 中序右边界
         * @return
         */
        private TreeNode process(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
            if (pl > pr) return null;

            // 前序遍历的第一个节点就是根结点
            int pRoot = pl;
            // 中序遍历中的根节点下标
            int iRoot = map.get(preorder[pRoot]);

            // 新建根节点
            TreeNode root = new TreeNode(preorder[pRoot]);
            // 左子树的节点数量
            int subLeftSize = iRoot - il;

            root.left = process(preorder, inorder, pl + 1, pl + subLeftSize, il, iRoot - 1);
            root.right = process(preorder, inorder, pl + subLeftSize + 1, pr, iRoot + 1, ir);

            return root;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0105_ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
        solution.buildTree(new int[]{3, 2, 1, 4}, new int[]{1, 2, 3, 4});
        solution.buildTree(new int[]{1, 2}, new int[]{1, 2});
        solution.buildTree(new int[]{1, 2}, new int[]{2, 1});
        solution.buildTree(new int[]{1, 2, 4, 5, 3, 6, 7}, new int[]{4, 2, 5, 1, 6, 3, 7});
        solution.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
    }
}